The present invention relates to methods and apparatuses for compressing data representing video or digital images. More specifically, the present invention relates to compressing data representing a set of images having a certain degree of similarity.
There are numerous areas of technology in which increasing volumes of image data must be processed and stored. This is particularly true with regard to medical radiological image data. The radiology department of a hospital may generate more than 500,000 digital images per year. One source estimates that a 1500-bed hospital may generate approximately 20 Terabytes of image data per year. Techniques for efficient classification, image processing, image database organization, and image transmission for analysis via telemedicine, have become important research areas.
The medical art has developed various Picture Archiving and Communication Systems (PACS) in an attempt to alleviate the problems associated with the creation of increasing volumes of medical image data. The functionality of most PACS is derived from the international Digital Imaging and Communication in Medicine (DICOM) standard. The DICOM standard specifies communications protocols, commands for image query and retrieval, storage standards, and similar parameters. However, prior art PACS still have many shortcomings. One serious disadvantage of conventional PACS is their insufficiency at reducing the large amounts of homogeneous data accumulating in radiological image databases. One method of reducing the amount of data in a database is to efficiently compress the image data prior to placing it in the database. Image data compression is also an important consideration in transferring the image from one location to another via network.
Typically, medical image data are compressed through conventional compression algorithms such as the standard Joint Photographic Experts Group (JPEG) algorithm. JPEG is presently the DICOM standard for data compression. JPEG utilizes Discrete Pulse Code Modulation (DPCM) for lossless and Discrete Cosine Transform (DCT) for lossy image compression. However, lossy compression is often avoided in medical imaging because of potential information loss, while lossless JPEG provides no means for compressing a series of similar images.
Alternate types of compression have been carried out with wavelet transforms. A wavelet transform decomposes a signal into a series of related waveforms similar to Fourier and DCT transforms decomposing a signal into a series of sine and cosine waveforms. The wavelet transform is based on a xe2x80x9cscaling functionxe2x80x9d xcfx86(x) and derived from it is a xe2x80x9cmother waveletxe2x80x9d "psgr"(x) satisfying the recursion relationship:                                           φ            ⁢                          xe2x80x83                        ⁢                          (              x              )                                =                                    ∑              k                              xe2x80x83                                      ⁢                          xe2x80x83                        ⁢                                          q                k                            ⁢                              xe2x80x83                            ⁢              φ              ⁢                              xe2x80x83                            ⁢                              (                                                      2                    ⁢                    x                                    -                  k                                )                                                    ,                            (1a)                                                      ψ            ⁢                          xe2x80x83                        ⁢                          (              x              )                                =                                    ∑              k                              xe2x80x83                                      ⁢                          xe2x80x83                        ⁢                                          h                k                            ⁢                              xe2x80x83                            ⁢              φ              ⁢                              xe2x80x83                            ⁢                              (                                                      2                    ⁢                    x                                    -                  k                                )                                                    ,                            (1b)            
where constants hk uniquely define functions xcfx86(x), "psgr"(x) and constants qk, and different choices of admissible hk (i.e. an hk for which a solution exists) produce different solutions to eqn. (1a) and eqn. (1b). Given "psgr"(x), a basis of sub-band waveforms or wavelets is constructed as successive translations and dilations of the mother wavelet. Thus, each wavelet in the "psgr"(x)xe2x88x92generated wavelet basis is represented by the equation:
"psgr"j,k(x)=2j/2"psgr"(2jxxe2x88x92k),xe2x80x83xe2x80x83(2)
where k represents the degree of translation and j represent the degree of dilation. When an image I(x) is transformed with wavelet "psgr"(x), it is projected onto the v(x)-generated wavelet basis:                                           I            ⁢                          xe2x80x83                        ⁢                          (              x              )                                =                                                    ∑                                  j                  ,                  k                                                  xe2x80x83                                            ⁢                              xe2x80x83                            ⁢                                                w                                      j                    ,                    k                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  x                  )                                                      =                                          ∑                                  j                  ,                  k                                                  xe2x80x83                                            ⁢                              xe2x80x83                            ⁢                                                w                                      j                    ,                    k                                                  ⁢                                  xe2x80x83                                ⁢                                  2                                      j                    /                    2                                                  ⁢                                  xe2x80x83                                ⁢                ψ                ⁢                                  xe2x80x83                                ⁢                                  (                                                                                    2                        j                                            ⁢                                              xe2x80x83                                            ⁢                      x                                        -                    k                                    )                                                                    ,                            (        3        )            
where wj,k is the coefficient associated with each wavelet In signal compression (and particularly in image signals), the common use of integer precision requires the coefficients wj,k to be integers, which can be always achieved in eqn. (3) with xe2x80x9cwavelet coefficient lifting.xe2x80x9d Wavelet coefficient lifting is well-known in the prior art as can be seen from publications such as xe2x80x9cWavelet Transforms that Map Integers to Integersxe2x80x9d by R. C. Calderbank, Ingrid Daubechies, Wim Sweldens, and Boon-Lock Yeo, in xe2x80x9cApplied and Computational Harmonic Analysisxe2x80x9d (ACHA), Vol. 5, Nr. 3, pp. 332-369, 1998. The number of wavelets N representing an image is generally equal to the number of elements (e.g. pixels) making up the image. A less formal, but more convenient manner of representing the wavelet transform of an individual image I(x) is to use a single index i instead of index pairs (j,k):                                           I            ⁢                          xe2x80x83                        ⁢                          (              x              )                                =                                    ∑                              i                =                1                            N                        ⁢                          xe2x80x83                        ⁢                                          w                i                            ⁢                              xe2x80x83                            ⁢                              ψ                i                            ⁢                              xe2x80x83                            ⁢                              (                x                )                                                    ,                            (        4        )            
where "psgr"i(x) still represents a particular wavelet, wi represents the wavelet coefficient associated with that wavelet, i is an integer from 1 to N, and the variable x represents each individual pixel position of the image.
FIG. 1 illustrates conceptually a patient""s head 1 and a series of horizontal brain CT images I(1), I(2), to I(m) taken therefrom. Each image may be represented by a wavelet equation such as equation (4). Thus, image I(1) may be represented as I(1)=w1(1)"psgr"1+w2(1)"psgr"2+. . . +wN(1)"psgr"N, and image I(m) may be represented as I(m)=w1(m)"psgr"1+w2(m)"psgr"2+. . . +wN(m)"psgr"N, as indicated in FIG. 1. Decomposing images into a wavelet transform with the above equations is well known in the art. One conventional software program which will determine the coefficients of an image for a given mother wavelet is MATLAB(copyright), produced by The MathWorks, Inc. of 24 Prime Park Way, Natick, Mass. MATLAB(copyright) implements a xe2x80x9cfast wavelet transformxe2x80x9d technique which is well know in the art. The fast wavelet transform also orders the wavelet sub-bands in a sequence of lowest spatial frequency to highest spatial frequency. It will be understood that given the mother wavelet form and the wavelet coefficients w1, w2, w3. . . wN, the inverse transform may be applied and the original image reconstructed. However, transforming an image from the original pixel into the wavelet coefficient representation (eqn. (4)), often reduces redundant information typically present in images, thus providing the means for more compact image representation, i.e. compression. If the mother wavelet is known, the image is easily recovered from its wavelet coefficients with the inverse wavelet transform.
However, despite developments of new PACS and the introduction of wavelet transforms in data compression, the prior art has still failed to efficiently represent the inter-image informational redundancy that is usually present in any image database. This redundancy arises from the fact that radiological images typically comprise a set or xe2x80x9cstudyxe2x80x9d of different views or numerous xe2x80x9cslicesxe2x80x9d of a particular organ. For example, a CT scan study of the brain may consist of approximately 150 vertical slices and approximate 30 horizontal slices. Each of these views or slices is a digital image requiring a significant number of bytes to represent: one view in an X-ray study of the chest may require as much as 10MB and thousands of such X-ray studies could be expected in a hospital""s database.
It has been found that, statistically, the mean difference between images of the same organ in different individuals is much smaller than the difference between two unrelated images, such as images of two famous paintings. The lack of difference (or the similarity) of two images can be quantified by the correlation between the two images, where a correlation of zero reflects absolutely no similarity and a correlation of one reflects identical images. It was observed that the correlation between many images of the same organs, such as the brain or lungs, in different individuals will be at least between 0.50 and 0.90 and possibly higher than 0.90. Additionally, the correlation between different images of the same organ in a single study may also be between 0.50 and 0.90 and possibly higher than 0.90. Thus, there is a large set redundancy in a database containing thousands of chest X-ray images or CT scan brain images. It would constitute a significant advance in the art to provide a data compression technique which took advantage of these naturally occurring redundancies in radiological images and other similar sets of images.
It has also been discovered that particular transforms more closely approximate a set of similar images than other transforms. In particular, certain mother wavelets more accurately decompose a set of images of a given human organ than other mother wavelets. Thus, for a particular organ, e.g. the brain, a mother wavelet "psgr"(x) having a particular set of constants hk in eqn. (1b) will better represent brain images than a mother wavelet having a different set of hk. Those skilled in the art will recognize that data compression involving wavelet transformations will be more efficient if the compression routine utilizes a mother wavelet which more efficiently and more accurately decomposes the set of images being compressed.
It is an object of this invention to implement image data compression using wavelet transforms in a novel method and apparatus.
It is a further object of this invention to implement image data compression in a set of similar images by taking advantage of naturally recurring redundancies in the set of images.
Finally, it is an object of this invention to implement image data compression by utilizing a wavelet transform which closely represents the set of images being compressed.
Therefore, the present invention provides a method of compressing image data. The method includes providing a set of individual images wherein there is a correlation between images of approximately greater than 0.5. Many of the images of organs may have a correlation of between 0.5 and 0.9. A wavelet transform is applied to a reference image of the set in order to determine a series of reference coefficients wi(1). The same wavelet transform is applied to an adjacent image of said set in order to determine another series of coefficients wi(2). It is implied that a wavelet transform can be combined with xe2x80x9cwavelet coefficient liftingxe2x80x9d or truncation to a chosen coefficient precision. The series of coefficients wi(kxe2x88x921) and wi(k) (for all kxe2x89xa72) are then compared in order to determine a coefficient b(k) and a series of coefficients ci(k), such that wi(k) may be determined from the relationship wi(k)=└b(k)wi(kxe2x88x921)┘+ci(k). Alternatively, b(k) may beset equal to one rather than be determined. The coefficients for the reference image wi(1), b(k) (if b(k) is not equal to one), and ci(k) are then entropy encoded in order to form a compressed set of image data.
The present invention also provides an apparatus for compressing image data. The apparatus has a memory circuit capable of storing a set of images. There is also a wavelet transformation circuit which transforms the k-th image of the set into a series of wavelet coefficients wi(k). Assuming b(k) is equal to one, a difference coefficient circuit determines the difference coefficient di(k) by subtracting a previous image wavelet coefficient wi(kxe2x88x921) from an adjacent image wavelet coefficient wi(k). A still further circuit determines a value n such that di(k) is determined for all values of 1 less than i less than n. Finally, an entropy encoding circuit encodes n, the coefficients wi(1), di(k) for 1 less than i less than n and wi(k) for n less than i  less than N, thereby forming a compressed set of image data.